Skip to main content

Half-edge graph

A TypeScript implementation of the Halfedge structure for three.js geometries.

Overview​

The HalfedgeGraph is a fork of three-mesh-halfedge by LokiResearch, released under the MIT license. It provides a robust solution for working with halfedge data structures in three.js geometries.

Key Changes from the Original​

The original logic and API were preserved, but component names were updated to avoid naming conflicts with the web-3d-std-lib API:

  • HalfEdgeDS → HeGraph
  • Vertex → HeVertex
  • Face → HeFace
  • Halfedge → HeEdge

Supported Geometries​

The HalfedgeGraph supports a wide range of geometries, including:

  • Multiple edges between the same vertices
  • Isolated polygons, edges, and vertices
  • Mixed wireframe and polygonal geometries
  • Polygons with arbitrary numbers of vertices and edges
  • Polygons meeting only at a single vertex

Examples​

Visualizations and Applications​

Code Snippets​

Example 1: Building the Halfedge Structure​

import { BoxGeometry } from "three";
import { HeGraph } from "@stg-oneportal/web-3d-stdlib";

// Build the Halfedge structure from a BoxGeometry
const geometry = new BoxGeometry();
const halfedgeGraph = new HeGraph();
halfedgeGraph.setFromGeometry(geometry, 1e-10);

Example 2: Extracting Boundary Halfedges​

const halfedgeGraph = new HeGraph();
halfedgeGraph.setFromGeometry(mesh.geometry);

// Get the boundary edges (keep only one halfedge for each pair)
const boundaries = new Set<HeEdge>();
for (const halfedge of halfedgeGraph.halfedges) {
  if (!boundaries.has(halfedge.twin) && !halfedge.face) {
    boundaries.add(halfedge);
  }
}
console.log("Boundary halfedges", boundaries);

Example 3: Identifying Front Faces​

const halfedgeGraph = new HeGraph();
halfedgeGraph.setFromGeometry(mesh.geometry);

// Get the camera position in mesh's space
const localCameraPos = mesh.worldToLocal(camera.position.clone());

// Get the front faces
const frontFaces = [];
for (const face of halfedgeGraph.faces) {
  // Position is considered in the geometry's local system
  if (face.isFront(localCameraPos)) {
    frontFaces.push(face);
  }
}
console.log("Front faces", frontFaces);